The present invention relates to processing of digital information for printing by laser printers or the like and, more particularly, to anti-aliasing the digital information. As known in the art, laser printers include a print engine having a laser beam which is selectively turned on and off to subsequently create printed dots on a sheet of paper. Typically, the laser scans the paper in a row-by-row fashion in a manner similar to the video rasterization for cathode ray tubes. As detailed below, the laser scans across a given row, and a darkened spot appears along the row where the laser is turned on, while a white spot appears along the row where the laser is turned off. FIGS. 1A and 1B illustrate the concept of anti-aliasing in connection with a printer system, such as laser printers, ink-jet printers, or other such binary systems. In general, anti-aliasing is a method by which jagged edges are smoothed to create a more accurate, or more appealing, appearance in printed matter. FIG. 1A illustrates a pattern before anti-aliasing, while FIG. 1B illustrates the same pattern after anti-aliasing is applied to a portion of the pattern. These Figures, as well as anti-aliasing in general, are discussed immediately below.
FIG. 1A illustrates the top left corner of a pre-corrected image 10 to be printed on a page designated generally at 12. For purposes of explanation, page 12 is subdivided as a matrix including a series of rows (1 through N) and columns (1 through M). Locations, or pixels, within this matrix are referred to in this document according to matrix designation, that is, as "(row, column)." For example, the uppermost darkened pixel in image 10 is at location (0,3), while the lowermost darkened pixel in image 10 is at location (8,5). For purposes of this document, note that a pixel with a darkened state is referred to a "black pixel" while a pixel with a non-darkened state is referred to as a "white pixel." Under current technology, pixels on the order of 600 by 600 dots per inch ("dpi") are printed in this manner. Thus, the few pixels of FIGS. 1A and 1B are vastly magnified to illustrate various concepts.
The pixels of image 10 are commonly stored as bits in a bitmap memory, and the memory locations are organized in a fast scan-line manner to map the desired image onto paper 12. Note that the term "fast scan-line manner" used within this document is based on the term fast scan direction known in the art. Particularly, the fast scan direction is the direction in which the printed image is formed on a page, that is, the direction in which the print mechanism (e.g., laser) scans with respect to paper 12. The fast scan direction is always perpendicular to the direction a piece of paper moves through the printer, regardless of the orientation of the page (i.e., portrait or landscape) . Note also that the direction the paper moves through the printer is called either the "slow scan direction" or the "process" direction. Given this terminology, note therefore that the statement that the pixels are organized in the fast scan-line manner indicates that the memory orientation of pixel rows is the same as the lines as they will eventually be printed (i.e., scanned) across paper 12. Thus, by stating that the memory locations are organized in a fast scan-line manner, it is meant that the bits in the memory are addressable such that a first byte corresponds to the first eight bits of image 10 to be scanned (by the printing apparatus) across the top of page 12 (i.e., in the fast scan direction), a second byte corresponds to the second eight bits of image 10 to be scanned, and so forth. For a letter or other typical portrait document, the scan creates a horizontal image and, thus, the memory storage may be thought of as horizontally oriented (i.e., from the left of the page image to the right of the page image). Of course, for a landscape printing, the fast scan direction is still across the width of the page, but the actual printed image appears vertically oriented and, thus, the memory storage may be thought of as vertically oriented (i.e., from the bottom of the page image to the top of the page image). In either instance, however, the memory storage is oriented in the same manner as the fast scan-line direction as that term is defined above.
For printing the memory-stored bits, in each instance, one byte of memory corresponds to eight bits to be printed in a fast scan-line direction along a piece of paper. In this regard, one of many available types of serial interface circuits reads bytes from the bitmap memory in a byte-by-byte fashion along the scan-line rows of the memory, and for each byte, outputs a serialized data stream to the printer laser beam. Typically, the serial interface circuit outputs a laser on signal when a black pixel is encountered in memory, and a laser off signal when a white pixel is encountered in memory. In some instances, however, systems operate in a negative mode, where a laser off signal eventually results in a black pixel (rather than white) . In addition, if the video is digitally inverted somewhere between the memory system and a positive developing system, then a zero in memory results in black. In any event, regardless of the conversion from binary storage state to print state, without implementing anti-aliasing technology, therefore, one skilled in the art will readily appreciate that as the laser is controlled in any of these types of fashions, image 10 from the bitmap memory is recreated onto page 12. Given the varying type of systems, for purposes of this document, and for simplicity, it is assumed that a binary 1 stored in memory corresponds to a black pixel and a laser on signal, and a binary 0 stored in memory corresponds to a white pixel and a laser off signal. One skilled in the art, however, may easily apply the teachings of the present invention to other systems such as those set forth above (e.g., negative mode, etc.).
The serial print information must account for timing mechanisms included with typical laser print engines. For example, the print engine has an associated clock (usually provided by the printer) which provides a synchronization signal indicating when the laser is to be on or off. To draw a darkened area, an on signal is coupled to the laser synchronous to the clock and for a predetermined duration. For purposes of this document, this predetermined duration is referred to as a "pixel time," meaning the amount of time the laser is on to fully complete a pixel on the printed page. Thus, when the laser is on for an entire pixel time, the laser sweeps from the left vertical border of a matrix location to the right vertical border of a matrix location, thereby creating a complete pixel. As known in the laser printer art, in actuality, the laser reacts with a photosensitive material on a drum, and the printer toner subsequently adheres to the location of the reaction, thereby creating the printed pixel.
As mentioned above, anti-aliasing technology smoothes the otherwise jagged edges of matter to be printed. For example, in FIG. 1A, one can readily recognize a jagged edge created between the pixel at (2,3) and the pixel at (3,4). However, FIG. 1B illustrates image 10 after correction; that is, after anti-aliasing, a smoother diagonal line can be created at these locations by drawing only partial pixels, that is, by only partially filling a location within the matrix to create the appearance of a shifted pixel. Particularly, systems have been recently developed which turn the laser on only during a portion of the pixel time; consequently, only a portion of the area is darkened between the left and right vertical borders of a matrix location. Further, a partial pixel may be left justified within the vertical borders by turning the laser on synchronous with the clock (i.e., at the start of the pixel time), but turning it off before the end of the pixel time. Similarly, a partial pixel may be right justified within the vertical borders by turning the laser on after some delay from the start of the pixel time, and turning it off and the end of the pixel time. Thus, in FIG. 1B, a partial pixel is right justified at location (2,3), and combines with a left justified partial pixel at location (2,4) to create the appearance of a single pixel shifted slightly to the right when compared with the original pixel at location (2,3) in FIG. 1A. Similarly in FIG. 1B, a partial pixel is right justified at location (3,3) and combines with a left justified at location (3,4) to create the appearance of a single pixel shifted slightly to the left when compared with the original pixel at location (3,4) in FIG. 1A. While not shown in FIG. 1B, one skilled in the art will also recognize that the same anti-aliasing technique could be applied to the jagged edge formed between locations (5,4) and (6,5) of FIG. 1A as well.
Having explained some basic principles regarding anti-aliasing, FIG. 2 illustrates a prior art anti-aliasing architecture designated generally at 14. Anti-aliasing architecture 14 includes a bitmap memory 16, a serial interface circuit 18, an anti-aliasing circuit 20, a buffer memory 22, and a print engine 24. Bitmap memory 16 stores bit-mapped data in the fashion described above. For example, bitmap memory 16 may store enough image data corresponding to a single page (e.g., 8.5 by 11.0 inches) of print.
Bitmap memory 16 is coupled to serial interface circuit 18. Serial interface circuit 18 reads one fast scan-line byte at a time from bitmap memory 16, and then serializes each bit of the byte by outputting one bit per pixel time. Thus, the serialized data represents the on/off signals to control the laser beam of print engine 24. Moreover, because of the fast scan-line orientation of the bitmap memory, when a byte is read from the bitmap memory and serialized, it is duplicated in the fast scan-line direction across the page by the on/of operation of the laser (and subsequent laser printer techniques known in the art).
In the prior art, however, anti-aliasing circuit 20 is interposed between serial interface circuit 18 and print engine 24. Typically, anti-aliasing circuit 20 is a chip which may be connected in such an intermediary fashion to add anti-aliasing functionality to a system which otherwise would not include such a feature. Anti-aliasing circuit 20 is also coupled to a buffer memory 22 which is commonly an external SRAM. In general, anti-aliasing circuit 20 intercepts the serialized data from serial interface circuit 18 and stores it in buffer memory 22. Further, anti-aliasing circuit 20 performs the smoothing function described above by modifying the intercepted data as explained below in connection with FIGS. 3A-3E. Anti-aliasing circuit 20 then outputs its own serialized data to print engine 24, with modifications made in accordance with the particular anti-aliasing technique employed by circuit 20. Print engine 24 includes the mechanical components of a printer, such as a laser beam, which are then controlled by the serialized data to form pixels on a page of paper.
Note that configuration 14 of FIG. 2 suffers drawbacks because data is intercepted by anti-aliasing circuit 20 after it is serialized. Particularly, precise sampling of the serial data is required to ensure pixels do not change from black to white or white to black due to sampling near the edge of a pixel rather than at the center of a pixel. Moreover, because image data is intercepted, sampled, buffered, processed, and retransmitted serially, there is an added delay. This delay causes a downward image shift on the paper because the first several rows of data, transmitted by serial interface circuit 18 and intended for the top of the paper, are intercepted and processed before being received and printed by print engine 24. During these intermediate steps, print engine 24 scans white lines across the page (because it normally would be receiving data during this intermediate period) and, only thereafter does the actual image commence printing. Thus, the addition of these white lines across the top of the page effectively shifts the printed image downward. As evident from the discussion below, there is also a shift to the right because several columns of data are similarly required.
FIGS. 3A-3E illustrate a prior art technique for performing the functions of anti-aliasing, namely, identifying a pattern to be corrected, and making a correction to the center pixel of that pattern. Particularly, FIG. 3A illustrates image 10 and page 12 of FIG. 1A, but further includes a sample window 26 (shown by darkened lines). In the example of FIGS. 3A-3E, sample window 26 is a twenty-five (i.e., five by five) pixel window.
As detailed below, sample window 26 sweeps across, and down, the intended pixel representation stored in memory in a raster-like fashion, and determines for each subset of twenty-five pixels whether an adjustment should be made to the center pixel of the patterns represented by the subset. As each determination is made, if no adjustment is to be made, then anti-aliasing circuit 20 outputs the same pixel information as was stored for the given center pixel. Thus, if the center pixel was originally black (i.e., laser on), then anti-aliasing circuit 20 outputs a laser-on signal to print engine 24. Similarly, if the center pixel was originally white (i.e., laser off), then anti-aliasing circuit 20 outputs a laser-off signal to print engine 24. To the contrary, if an adjustment is to be made to the center pixel (i.e., to cause smoothing), then anti-aliasing circuit 20 outputs different pixel information from that received from serial interface circuit 18. For example, an originally black pixel may need to be converted to a one-half dot which is left justified within the vertical borders of the pixel. As discussed above, therefore, anti-aliasing circuit 20 outputs a laser-on signal for the first half of the pixel time, and a laser-off signal for the second half of the pixel time.
Before proceeding with the example of FIGS. 3A-3E, note that image 10 of FIG. 1A is also used in FIGS. 3A-3E. Note further that although sample window 26 is shown overlaying page 12, it should be understood that, in operation, sample window 26 is actually considering the stored representation of the pixels located in buffer memory 22. The prior art technique for storing the pixel representation in buffer memory 22 is discussed in detail below in connection with FIGS. 4A-4D. In overall operation, the anti-aliasing function samples this memory depiction of the pixels and determines if the pixel in the center of the sample, when printed, should differ from that stored in memory. If a change in center pixel state is desirable, print engine 24 is so controlled such that the actual printed center pixel differs from the corresponding center pixel in memory; however, note that the corresponding pixel data in the memory is unchanged.
Also before proceeding, note that sample window 26 is not a physical device, but instead is a representation of the functionality of anti-aliasing circuit 20, that is, the function of reviewing a stored subset of pixels to identify whether the center pixel of the subset requires correction when printed.
Referring to FIG. 3A, sample window 26 is shown in a first demonstrative position which encompasses the upper and left twenty-five pixels to be printed on page 12. Before proceeding, note that the first demonstrative position shown of window 26 is chosen for simplifying the discussion, but is not necessarily the initial position across page 12. Particularly, in the present invention, to begin the scan, window 26 is situated so that its center location aligns with the pixel located at location (0,0); in other words, the upper two rows and left two columns of sample window 26 would, in effect, extend beyond page 12, thereby encompassing only nine pixels of page 12, with the remaining sixteen pixels extending outside of window 26. Further, when the window locations extend beyond the image as described, those locations beyond the image are assumed to be in a state (e.g., white) and the actual pixels of image 10 included at this beginning step are considered as combined with these assumed white pixels for purposes of anti-aliasing. In prior art systems, however, it is believed that sample window 26 (and its associated circuitry) is merely disabled when sample window 26 is not entirely over a portion of image 10 and, thus, anti-aliasing corrections are not permitted along the edges of image 10.
Referring now to the first demonstrative position of FIG. 3A, in this position, sample window 26 (and associated circuitry) determines whether the pattern of pixels having a center pixel at location (2,2) requires correction to that center pixel. Referring now to the pre-correction image 10 of FIG. 1A and the post-correction image 10 of FIG. 1B, note that no change is made to the center pixel (i.e., at location (2,2)) of FIG. 3A and, thus, no anti-aliasing correction is required in this instance. Thus, because the memory stored center pixel is white, then anti-aliasing circuit 20 outputs a laser-off signal to print engine 24 to print an unchanged (i.e., white) pixel. Thereafter, sample window 26 shifts one pixel column to the right as further discussed immediately below in connection with FIG. 3B.
In FIG. 3B, the center pixel of sample window 26 is at location (2,3). In this position, and as indicated in FIG. 1B, a correction is required. Thus, the pixel subset encompassed by sample window 26 is recognized as a pattern requiring correction at its center location. To accomplish the correction, anti-aliasing circuit 20 consults an internal table of registers known as dot modulation registers ("DMRs"). Each DMR is programmed with a sequence of bits which are output during a single pixel time and, thus, modulate the laser beam according to the values of the bits. For example, a DMR value of 00001111 turns off the laser beam for the first half of the pixel time (in response to the four binary zeroes) and turns on the laser beam for the second half of the pixel time (in response to the four binary ones). Thus, if eight bits are used, each bit is transmitted to the laser during a 1/8th pixel time, thereby approximating control of the laser in 1/8th increments between the left and right vertical borders of the pixel.
In the example of FIG. 3B, the corrected pixel to be located at the center location of (2,3) is a 5/8 right justified dot (as confirmed by viewing FIG. 1B). Thus, in response to detecting the pixel subset in window 26, a DMR within anti-aliasing circuit 20 outputs a byte equal to 00011111, thereby turning the laser off for the first 3/8 of the pixel time, and on for the last 5/8 of the pixel time. Thus, one skilled in the art will appreciate that the partially darkened area in location (2,3) of FIG. 1B is printed on page 12 rather than the original fully darkened location (2,3) of FIG. 1A. Thereafter, once again sample window 26 shifts one pixel to the right, as discussed immediately below in connection with FIG. 3C.
In FIG. 3C, the center pixel of sample window 26 is at location (2,4). Once again, a center pixel correction is required. In the example of FIG. 3C, a different DMR is called to output the necessary sequence for a left-justified 3/8 darkened dot within location (2,4). Thus, the selected DMR outputs a value of 11100000, thereby causing print engine 24 to print the left-justified 3/8 darkened dot instead of the white pixel originally stored in bitmap memory 16 and serialized by interface circuit 18.
The process described above in connection with FIGS. 3A-3C continues across the entire top five rows of the matrix, with window 26 advancing one column at a time and evaluating its center pixel in each instance. Thus, the entirety of row 2 of pixels are individually considered for anti-aliasing as the center location of window 26 scans across such pixels. For purposes of simplification, however, each such action is not shown in the Figures.
Once sample window 26 fully scans the top five rows as discussed above, it moves vertically down one row, thereby aligning its center pixel with row 3 of the pixels. For a brief demonstration, FIG. 3D illustrates sample window 26 in its initial position after descending one row in this fashion. Now, therefore, location (3,2) is the center location of sample window 26 and, given the pixel subset encompassed by sample window 26 in this position, once again a determination is made as to whether a change is necessary to smooth in the manner described above. For the example shown (as indicated in FIG. 1B), no change is necessary and, thus, anti-aliasing circuit 20 outputs the same binary state as is stored for the center pixel, namely, a white pixel.
Lastly, FIG. 3E illustrates the location of sample window 26 after FIG. 3D, and further demonstrates that sample window 26 continues in its raster-like fashion across rows 1-5, with row 3 aligned with its center pixel. Thus, in FIG. 3E, the pixel subset encompassed by sample window 26 is detected as having a center location (i.e., (3,3)) which requires modification and, thus, circuit 20 acts in accordance with the principles set forth above. One skilled in the art will readily appreciate that sample window 26 continues in this fashion, that is, scanning a row, descending a row and scanning the successive row, and so forth. Thus, an entire page of rows is scanned and smoothed, when necessary, with the exception of the last two rows which cannot align with the center pixel of sample window 26.
As mentioned above, the prior art anti-aliasing circuit 20 intercepts the serialized data from serial interface circuit 18 and stores the intercepted information into buffer memory 22. The following discussion of FIGS. 4A-4D details the methodology of such storage and, thereby, introduces certain aspects of the prior art which are overcome by embodiments of the present invention. FIG. 4A illustrates a detailed example of buffer memory 22 which consists of M bytes of memory storage. For purposes of illustration, these bytes are labeled 1 through M, and are addressed according to such designation. As detailed above, buffer memory 22 stores the information in a format that may be scanned by sample window 26. FIGS. 4B-4D demonstrate the prior art storage methodology.
Recall that anti-aliasing circuit 20, and therefore buffer memory 22, receive serialized information from bitmap memory 16. This information is coded as a binary 1 to indicate a black pixel, and a binary 0 to indicate a white pixel. Thus, without an anti-aliasing feature, the bits from bitmap memory 16 would be printed by print engine 24 directly onto page 12, thereby creating an image on paper 12 exactly as stored in bitmap memory 16. However, buffer memory 22 is M bytes wide and stores each incoming bit in the successively addressed locations as described with respect to FIGS. 4B-4D, below.
With reference to FIG. 4B, buffer memory 22 is shown containing the first 1 through M serialized bits from bitmap memory 16 (via serial interface circuit 18). Note that each incoming bit is stored in a different memory byte, and at the least significant bit location of such corresponding byte. For purposes of convention, the bits are shown as "B", and a subscript is added wherein the first character represents the row to be printed while the second character represents the column to be printed. For example, bit B.sub.0,0 is to be printed at location (0,0), bit B.sub.0,1 at location (0,1), and so forth. Thus, the first row of bits, namely B.sub.0,1 through B.sub.1,M, are initially stored along one row of the memory locations, but in separate memory byte locations as shown.
Recall that buffer memory 22 is used to provide a temporary buffer for storing at least a portion of the image so that the portion may be scanned by a sample window. Thus, as the second row of serialized bits arrive, they must be located "under" the first row of bits in order to re-create the bitmapped image for scanning. Toward that end, the prior art shifts the first row of bits upward by one row, and then inserts the second row of bits along the least-significant bit row as shown in FIG. 4C. To accomplish the shifting result in a memory, the prior art performs a read-modify-write operation as each bit in the second row arrives. For example, as bit B.sub.1,0 arrives, memory byte 0 is read, the read data is modified to include the combination of B.sub.0,0 and B.sub.0,1, and the result is written back to byte 0. Thus, if B.sub.0,0 =1, and B.sub.1,0 =0, then a binary 00000001 (i.e., B.sub.0,0) is read from byte 0, and is combined as the second significant bit to the incoming 0 (i.e., B.sub.1,0), and the combined 00000010 is written back to byte address 0. This operation continues so that M read-modify-write operations are necessary to store the second row of bits into buffer memory 22, with the result shown in FIG. 4C.
As is known in the art, the read-modify-write operation is a time costly event because two memory accesses are required (i.e., one to read, one to write), and because data buses must be reversed in direction to perform the separate read and write operations. Indeed, in one aspect of the present invention, it is recognized that technological advancements are requiring a faster clock rate for providing data to print engine 24. At faster clock rates, it may be impossible, or at least economically undesirable, to perform a sufficient number of read-modify-write operations and still timely supply data out of anti-aliasing circuit 20 to print engine 24. As detailed below, the present invention eliminates the necessity of the read-modify-write operations and, in doing so, vastly enhances the ability to provide anti-aliased serial data at higher clock rates.
Note that the operation described in connection with FIGS. 4B and 4C continues as buffer memory 22 fills as illustrated in FIG. 4D (for simplicity of the drawing, only the first two and last two rows of bits are labeled). Thus, after eight successive rows are filled, the first line of bits from FIG. 4A are moved from the bottom to the top of buffer memory 22. Note, therefore, that a filled buffer memory 22 provides a region for sampling by sample window 26 as shown in FIGS. 3A-3E. Indeed, if the sample window is a five by five bit window as shown in FIGS. 3A-3E, sampling in the prior art manner described (i.e., disabling sampling until the sample window fully encompasses an image) may commence only after five rows of bits are stored in buffer memory 22 because, at such a point, sufficient data is collected to begin determining whether center pixel correction is required. However, additional rows may be used because of availability, timing considerations, larger sampling windows, as well as other bases known in the art.
Once each of the eight rows of buffer memory 22 is filled as shown in FIG. 4D, note that the next row of incoming information is again written into the least significant location of the respective bytes using respective read-modify-write operations. Consequently, the information which is eight rows earlier and stored at the top of buffer memory 22 in FIG. 4D is shifted out of the memory and, thus, for each successive line of serialized data, only it as well as the seven preceding lines of bits are retained.
Given the technique of FIGS. 4A-4D, note that a filled buffer memory 22 stores the pixel data in a non-scan-line fashion, as opposed to the fast scan-line fashion of bitmap memory 16. By stating that the buffer memory 22 locations are organized in a non-scan-line manner, it is meant that the pixels within an addressable location within buffer memory 22 correspond to a perpendicular representation of how those pixels would appear when printed in the fast scan-line direction by print engine 24 (i.e., the pixels are stored in buffer memory 22 in the slow scan direction).
Due to the non-scan-line disposition of buffer memory 22, note the effect on the operation of sample window 26 as shown in FIGS. 3A-3E. In order to evaluate five columns of pixels (e.g., for a five by five pixel window), five bytes of buffer memory must be read. Note that the least significant bits of each of the five bytes constitute a fast scan-line row of pixels. Similarly, the most significant bits of each of the five bytes constitute a fast scan-line row of pixels and, indeed, each of the other respective significant bits of each of the five bytes constitute a fast scan-line row of pixels. Thus, by reading the five addressable locations, a window of bits is created having five columns and which is eight rows high (because each addressable location has eight bits).
The non-scan-line orientation of buffer memory 22 in the above fashion is inefficient for numerous reasons. First, as described above, the implementation requires numerous read-modify-write operations. Second, because each addressable location only stores one fast scan-line pixel, the number of memory locations must equal (or be greater than) the number of pixels which will be printed along a given line of paper. Thus, for an eleven inch wide piece of paper using 800 dots per inch, 8800 pixels may be printed and, hence, the memory must have 8800 byte locations. Third, the above example illustrates a potential waste of memory space. Particularly, commercially available memories are commonly eight bits wide (i.e., eight bits per byte). However, when using a five by five sample window, only five bits per byte are necessary. Thus, the three extra bits per byte are unnecessary and are wasting 37.5% of each byte.
In view of the above, there are numerous drawbacks and disadvantages of the prior art apparatus and methodology involved in anti-aliasing for binary printers. It is therefore an object of the present invention to provide an improved apparatus and methodology for anti-aliasing in binary printers.
It is a further object of the present invention to provide such an apparatus and methodology for processing image data before serialization.
It is a further object of the present invention to provide such an apparatus and methodology for reducing the time, hardware, and cost required for processing bitmap data to perform anti-aliasing.
It is a further object of the present invention to provide such an apparatus and methodology for simplifying the timing and control logic between data stored in a bitmap memory and a print engine while performing anti-aliasing.
It is a further object of the present invention to provide such an apparatus and methodology for permitting flexibility, efficiency, and programmability when detecting patterns represented by subsets of pixels.
It is a further object of the present invention to provide such an apparatus and methodology for reducing the amount of printer resource, such as printer toner, when printing hollowed features using anti-aliasing functionality.
Still other objects and advantages of the present invention will become apparent to those of ordinary skill in the art having references to the following specification together with its drawings.